package codeRandomThoughts.Test93复原IP地址;

import java.util.ArrayList;
import java.util.List;

public class Solution2 {
    List<String> result = new ArrayList<>();
    List<String> path = new ArrayList<>();
    int pathLen = 0;

    public List<String> restoreIpAddresses(String s) {
        backtracking(s, 0);
        return result;
    }

    public void backtracking(String s, int startIndex) {
        //回溯终止条件
        if (startIndex >= s.length() && path.size() == 4 && (pathLen == s.length())) {
            result.add(getRightPath(path));
        }

        //单层递归逻辑
        for (int i = startIndex; i < s.length(); i++) {
            String substring = s.substring(startIndex, i + 1);
            if (isValidIpAddress(substring)) {
                path.add(substring);
                pathLen += substring.length();
            } else {
                continue;
            }

            backtracking(s, i + 1);
            path.remove(path.size() - 1);
            pathLen -= substring.length();
        }
    }

    public String getRightPath(List<String> path) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < path.size(); i++) {
            sb.append(path.get(i));
            sb.append(".");
        }
        sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }

    public boolean isValidIpAddress(String s) {
        if (s.length() == 0) return false;
        if (s.length() > 1 && s.charAt(0) == '0') return false;
        if (s.length() > 3) return false;
        int num = Integer.parseInt(s);
        if (num >= 0 && num <= 255) return true;
        return false;
    }
}
